Bandwidth fragmentation is an important issue in the context of well-known optical networking standards, such as synchronous optical network (SONET) and synchronous digital hierarchy (SDH). These standards generally specify that bandwidth is provisioned as contiguous time slots on a given time division multiplexed link. For example, an STS-3c circuit and an STS-12c circuit require three and 12 contiguous time slots of STS-1 level granularity, respectively, where STS-1 denotes the lowest level granularity, and corresponds to the SONET basic transmission rate of 51.84 Mbps.
The provisioning of contiguous time slots is typically referred to as “contiguous concatenation,” and can result in fragmentation of a link. Such link fragmentation can cause a new traffic demand to be denied, even though a sufficient total number of slots exists, if there are insufficient contiguous slots to accommodate the demand.
Defragmentation refers generally to the process of reconfiguring the provisioned circuits so as to group the available time slots in a manner which better allows accommodation of additional demands.
Recently, virtual concatenation (VC) and link capacity adjustment scheme (LCAS) protocols have been developed which allow more efficient use of the existing fixed-bandwidth connections associated with circuit-switched SONET/SDH networks. The VC and LCAS protocols are described in greater detail in, for example, ITU-T standards documents G.707 and G.7042, respectively, both of which are incorporated by reference herein. These protocols avoid the fragmentation problem by eliminating the contiguous slot requirement. However, until all edge network elements support the new protocols, fragmentation will remain a serious issue for SONET/SDH networks.
U.S. Patent Application Publication No. 2004/0165540, cited above, discloses improved defragmentation techniques particularly well-suited for use in the SONET/SDH context. An illustrative embodiment comprises a defragmentation calculator, a candidate slot selector and a circuit mover. The defragmentation calculator calculates a defragmentation of a communication link, the defragmentation containing at least one granularity. The candidate slot selector finds reduced cost candidate slots for the at least one granularity. The circuit mover identifies target slots into which circuits occupying the candidate slots can be moved.
One particular example of a defragmentation algorithm of the type disclosed in U.S. Patent Application Publication No. 2004/0165540 is commonly known as “MöbiPack,” and is described in S. Acharya et al., “MöbiPack: Optimal Hitless SONET Defragmentation in Near-Optimal Cost,” IEEE Infocom, 2004, which is incorporated by reference herein. Such an algorithm may be implemented using the defragmentation calculator, candidate slot selector and circuit mover of the illustrative embodiment previously mentioned.
Despite the considerable advances provided by the defragmentation techniques disclosed in the above-cited references, a need remains for further improvements. For example, the MöbiPack algorithm performs defragmentation subject to granularity and alignment constraints imposed by the SONET/SDH standards, without requiring that any circuit be “torn down” and thus without causing any service disruption. This is referred to as “hitless” defragmentation, because the link is defragmented without any impact on live traffic. But an operational SONET/SDH network may impose additional constraints, which can make it difficult to determine if a link has been optimally defragmented. One such additional constraint is the constraint on allowable SONET/SDH rates on an interface, also referred to herein as the interface rate constraint. Thus, a defragmentation algorithm specifically designed to provide optimal hitless SONET/SDH defragmentation in the presence of an interface rate constraint would be highly desirable.